uncovering_cicadafandomcom-20200215-history
PGP TUTORIAL
What does PGP mean? What does it do? Pretty Good Privacy (PGP) is a data encryption and decryption computer program that provides cryptographic privacy and authentication for data communication. PGP is often used for signing, encrypting, and decrypting texts, e-mails, files, directories and whole disk partitions and to increase the security of e-mail communications. PGP and similar software follow the OpenPGP standard (RFC 4880) for encrypting and decrypting data. If you are already familiar with what PGP is, you may be ready to skip ahead to the section on how to use it.__TOC__ GNU Privacy Guard GnuPG is a complete and free implementation of the OpenPGP standard as defined by RFC4880 (also known as PGP). GnuPG allows to encrypt and sign your data and communication, features a versatile key management system as well as access modules for all kinds of public key directories. We recommend using GnuPG, regardless of your current operating system. '' However, the best explanation of it I've seen can be found below: (excerpt from Little Brother, a free novel by Cory Doctorow) ''"What would you do if you found out you had a spy in your midst? You could denounce him, put him up against the wall and take him out. But then you might end up with another spy in your midst, and the new spy would be more careful than the last one and maybe not get caught quite so readily. Here's a better idea: start intercepting the spy's communications and feed him and his masters misinformation. Say his masters instruct him to gather information on your movements. Let him follow you around and take all the notes he wants, but steam open the envelopes that he sends back to HQ and replace his account of your movements with a fictitious one. If you want, you can make him seem erratic and unreliable so they get rid of him. You can manufacture crises that might make one side or the other reveal the identities of other spies. In short, you own them. This is called the man-in-the-middle attack and if you think about it, it's pretty scary. Someone who man-in-the-middles your communications can trick you in any of a thousand ways. Of course, there's a great way to get around the man-in-the-middle attack: use crypto. With crypto, it doesn't matter if the enemy can see your messages, because he can't decipher them, change them, and re-send them. That's one of the main reasons to use crypto. But remember: for crypto to work, you need to have keys for the people you want to talk to. You and your partner need to share a secret or two, some keys that you can use to encrypt and decrypt your messages so that men-in-the-middle get locked out. That's where the idea of public keys comes in. This is a little hairy, but it's so unbelievably elegant too. In public key crypto, each user gets two keys. They're long strings of mathematical gibberish, and they have an almost magic property. Whatever you scramble with one key, the other will unlock, and vice-versa. What's more, they're the only keys that can do this -- if you can unscramble a message with one key, you know it was scrambled with the other (and vice-versa). So you take either one of these keys (it doesn't matter which one) and you just publish it. You make it a total non-secret. You want anyone in the world to know what it is. For obvious reasons, they call this your "public key." The other key, you hide in the darkest reaches of your mind. You protect it with your life. You never let anyone ever know what it is. That's called your "private key." (Duh.) Now say you're a spy and you want to talk with your bosses. Their public key is known by everyone. Your public key is known by everyone. No one knows your private key but you. No one knows their private key but them. You want to send them a message. First, you encrypt it with your private key. You could just send that message along, and it would work pretty well, since they would know when the message arrived that it came from you. How? Because if they can decrypt it with your public key, it can only have been encrypted with your private key. This is the equivalent of putting your seal or signature on the bottom of a message. It says, "I wrote this, and no one else. No one could have tampered with it or changed it." Unfortunately, this won't actually keep your message a secret. That's because your public key is really well known (it has to be, or you'll be limited to sending messages to those few people who have your public key). Anyone who intercepts the message can read it. They can't change it and make it seem like it came from you, but if you don't want people to know what you're saying, you need a better solution. So instead of just encrypting the message with your private key, you also encrypt it with your boss's public key. Now it's been locked twice. The first lock -- the boss's public key -- only comes off when combined with your boss's private key. The second lock -- your private key -- only comes off with your public key. When your bosses receive the message, they unlock it with both keys and now they know for sure that: a) you wrote it and b) only they can read it. It's very cool. The day I discovered it, Darryl and I immediately exchanged keys and spent months cackling and rubbing our hands as we exchanged our military-grade secret messages about where to meet after school and whether Van would ever notice him. But if you want to understand security, you need to consider the most paranoid possibilities. Like, what if I tricked you into thinking that my public key was your boss's public key? You'd encrypt the message with your private key and my public key. I'd decrypt it, read it, re-encrypt it with your boss's real public key and send it on. As far as your boss knows, no one but you could have written the message and no one but him could have read it. And I get to sit in the middle, like a fat spider in a web, and all your secrets belong to me. Now, the easiest way to fix this is to really widely advertise your public key. If it's really easy for anyone to know what your real key is, man-in-the-middle gets harder and harder. But you know what? Making things well-known is just as hard as keeping them secret. Think about it -- how many billions of dollars are spent on shampoo ads and other crap, just to make sure that as many people know about something that some advertiser wants them to know? There's a cheaper way of fixing man-in-the-middle: the web of trust. Say that before you leave HQ, you and your bosses sit down over coffee and actually tell each other your keys. No more man-in-the-middle! You're absolutely certain whose keys you have, because they were put into your own hands. So far, so good. But there's a natural limit to this: how many people can you physically meet with and swap keys? How many hours in the day do you want to devote to the equivalent of writing your own phone book? How many of those people are willing to devote that kind of time to you? Thinking about this like a phonebook helps. The world was once a place with a lot of phonebooks, and when you needed a number, you could look it up in the book. But for many of the numbers that you wanted to refer to on a given day, you would either know it by heart, or you'd be able to ask someone else. Even today, when I'm out with my cell-phone, I'll ask Jolu or Darryl if they have a number I'm looking for. It's faster and easier than looking it up online and they're more reliable, too. If Jolu has a number, I trust him, so I trust the number, too. That's called "transitive trust" -- trust that moves across the web of our relationships. A web of trust is a bigger version of this. Say I meet Jolu and get his key. I can put it on my "keyring" -- a list of keys that I've signed with my private key. That means you can unlock it with my public key and know for sure that me -- or someone with my key, anyway -- says that "this key belongs to this guy." So I hand you my keyring and provided that you trust me to have actually met and verified all the keys on it, you can take it and add it to your keyring. Now, you meet someone else and you hand the whole ring to him. Bigger and bigger the ring grows, and provided that you trust the next guy in the chain, and he trusts the next guy in his chain and so on, you're pretty secure. Which brings me to keysigning parties. These are exactly what they sound like: a party where everyone gets together and signs everyone else's keys. Darryl and I, when we traded keys, that was kind of a mini-keysigning party, one with only two sad and geeky attendees. But with more people, you create the seed of the web of trust, and the web can expand from there. As everyone on your keyring goes out into the world and meets more people, they can add more and more names to the ring. You don't have to meet the new people, just trust that the signed key you get from the people in your web is valid. So that's why web of trust and parties go together like peanut butter and chocolate." That does a pretty good job of explaining why you can trust it almost entirely (if you want to go beyond a reasonable doubt, the entire source code is freely available). But this guide doesn't go anything into how exactly I'm meant to get from this: -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 - From here on out, we will cryptographically sign all messages with this key. It is available on the mit keyservers. Key ID 7A35090F, as posted in a2e7j6ic78h0j. Patience is a virtue. Good luck. 3301 -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQIcBAEBAgAGBQJPBRz7AAoJEBgfAeV6NQkP1UIQALFcO8DyZkecTK5pAIcGez7k ewjGBoCfjfO2NlRROuQm5CteXiH3Te5G+5ebsdRmGWVcah8QzN4UjxpKcTQRPB9e /ehVI5BiBJq8GlOnaSRZpzsYobwKH6Jy6haAr3kPFK1lOXXyHSiNnQbydGw9BFRI fSr//DY86BUILE8sGJR6FA8Vzjiifcv6mmXkk3ICrT8z0qY7m/wFOYjgiSohvYpg x5biG6TBwxfmXQOaITdO5rO8+4mtLnP//qN7E9zjTYj4Z4gBhdf6hPSuOqjh1s+6 /C6IehRChpx8gwpdhIlNf1coz/ZiggPiqdj75Tyqg88lEr66fVVB2d7PGObSyYSp HJl8llrt8Gnk1UaZUS6/eCjnBniV/BLfZPVD2VFKH2Vvvty8sL+S8hCxsuLCjydh skpshcjMVV9xPIEYzwSEaqBq0ZMdNFEPxJzC0XISlWSfxROm85r3NYvbrx9lwVbP mUpLKFn8ZcMbf7UX18frgOtujmqqUvDQ2dQhmCUywPdtsKHFLc1xIqdrnRWUS3CD eejUzGYDB5lSflujTjLPgGvtlCBW5ap00cfIHUZPOzmJWoEzgFgdNc9iIkcUUlke e2WbYwCCuwSlLsdQRMA//PJN+a1h2ZMSzzMbZsr/YXQDUWvEaYI8MckmXEkZmDoA RL0xkbHEFVGBmoMPVzeC =fRcg -----END PGP SIGNATURE----- To 'I can completely trust that this message was sent from who they purport to be'? The important bit to remember here is that with 3301's messages, they aren't encrypted. Anyone can view them. But here we have that weird block of text at the bottom, with some random weird characters that don't appear to make any sense. Effectively, this block of text is an encrypted version of the message inside. This means that when your crypto software performs a check on it, it will decrypt that text to find that a) the message was sent from the person you're checking it off with, and b) that they sent this message exactly. If neither of these two tests return true, then the message was not sent from who this purports to be. Implementations As with almost any kind of open source software, there's going to be multiple people who have forked and edited the source code to create their own version of it which can run on multiple platforms, support different GUIs, maybe even different encryption algorithms. The recommended implementations for each platform can be found below: WINDOWS: gpg4win is the commonly accepted standard. Front-ends (like Kleopatra) are known for ignoring important signs of manipulated signatures. '''We recommend using the command line version of GnuPG.' '''LINUX:' GnuPG may already be installed on your machine. If you do not have it installed, you can install the 'gpg' package from your package manager. We strongly recommend that you use the command line version. However, the officially supported GUI is GPA. MAC: GPGTools is your only option here. It provides an awesome GUI and some great integration with OSX. Choosing a PGP implementation to verify with There are a lot of PGP implementations out there and they are not all the same. PGP is a sophisticated and complex standard and it is difficult to write proper cryptographic code that implements the standard. There are several possible issues you need to keep in mind if you want to verify a PGP signature with a high degree of confidence. One of the most unintuitive ways that a signature can appear legitimate when it really isn't is by malforming a message in various ways. A proper implementation will let you know by printing a warning, whereas a faulty or imprecise implementation will glance over the manipulation. On this wiki, we urge you to use the GnuPG implementation of PGP. It is free software, has a long track record of reliability and can be inspected by the general public. Other implementations may not have received as much code review and are therefore more likely to contain overlooked flaws. We further urge you to use the command line version of GnuPG if possible. It is known that front-ends like Kleopatra glance over signs of manipulated signatures and won't let you know. They are not suited for giving you all the information there is - they either ignore warnings or don't display them. It is currently believed that GnuPG detects a malformed message reliably and warns you accordingly. You should take these warnings seriously, and not ignore them. There are some parts of a PGP clearsigned message that do not invalidate the signature. For example, you can change the version header if one is present without the signature invalidating. How to use PGP for Cicada 3301 This, of course, is going to vary between different systems. Below I will provide the outlines of steps you can do, you should be able to find the corresponding stuff yourself in the programs. 1. GENERATE YOUR KEY PAIR Generating a PGP key was required in 2013's puzzle. You should probably do that and upload your key to as many servers as possible. NEVER REVEAL YOUR PRIVATE KEY TO ANYBODY. 2. GET 3301'S KEY 3301's key is officially available at MIT's keyserver . Import it to your software, you'll need it to verify any messages. 3. VERIFY ANY IMPORTANT MESSAGES You should take a look through the writeups of the previous puzzles for signed messages. Attempt to verify these with your PGP software. For most, you should get a confirmation. This can be done in the command line with $ gpg --verify filename An example can be seen here. = Note: LANG=en_US ''is not required. Our dear brotherBox is just German and wanted it to display in American English. = How do I make a PGP key? ''NOTE: NEVER REVEAL YOUR PRIVATE KEY TO ANYBODY NOTE: IT IS RECOMMENDED THAT YOU USE A FRESH EMAIL FOR PGP KEYS Here is an RSA key creation worksheet, to better understand the mathematics behind key creation and encryption/decryption process * https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html PGP Users: $ pgp --gen-key Please select what kind of key you want: (1) RSA and RSA (default) (2) DSA and Elgamal (3) DSA (sign only) (4) RSA (sign only) Your selection? 1''' RSA keys may be between 1024 and 4096 bits long. What keysize do you want? (2048) '''2048 Requested keysize is 2048 bits Please specify how long the key should be valid. 0 = key does not expire = key expires in n days w = key expires in n weeks m = key expires in n months y = key expires in n years Key is valid for? (0) 0''' Key does not expire at all Is this correct? (y/N) '''y You need a user ID to identify your key; the software constructs the user ID from the Real Name, Comment and Email Address in this form: "Heinrich Heine (Der Dichter) " Real name: Bob Smith Email address: bob@smith.com Comment: Hello World! You selected this USER-ID: "Bob Smith (Hello World!) " Change (N)ame, ©omment, (E)mail or (O)kay/(Q)uit? O''' You need a Passphrase to protect your secret key. Enter passphrase: '''****** Repeat passphrase: ****** Extra Information For... Windows Users: * http://www.gpg4win.org * http://www.gpg4win.org/doc/en/gpg4win-compendium_12.html If you want outgoing/incoming mail to be automatically encrypted/decrypted, install the Thunderbird email client and the Enigmail add-on. OS X Users: * https://gpgtools.org/ Linux Users: * http://stllug.sluug.org/meeting_notes/1996/0718/pgp_how.html * http://www.dewinter.com/gnupg_howto/english/GPGMiniHowto.html YouTube Videos and other links about PGP and RSA Nox Populi's video on using PGP to verify cicada 3301: * https://www.youtube.com/watch?v=3yN4uMMsK8I How did the NSA hack our emails? * Part 1: http://youtu.be/ulg_AHBOIQU * Part 2: http://youtu.be/1O69uBL22nY Wikipedia articles: * https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange * https://en.wikipedia.org/wiki/Pretty_Good_Privacy * https://en.wikipedia.org/wiki/GNU_Privacy_Guard * https://en.wikipedia.org/wiki/RSA_%28algorithm%29 Just tell me how the PGP magic works! * http://searchsecurity.techtarget.com/definition/RSA Extra information on PGP: * https://www.gpg4win.org/doc/en/gpg4win-compendium_11.html * https://bitcointalk.org/index.php?topic=297434.0 * http://www.youtube.com/watch?v=vgTtHV04xRI&list=ECB4D701646DAF0817 * http://youtu.be/M7kEpw1tn50?t=54s * http://youtu.be/Fty107Us7oc?t=10m25s * http://youtu.be/Fty107Us7oc?t=9m18s * http://vimeo.com/56881481 Or, a more simple version: * Gambling with Secrets: Part 2/8 (Prime Factorization) * Gambling with Secrets: 8/8 (RSA Encryption) * Encryption and HUGE numbers - Numberphile (very nicely explained the mathematics behind the RSA encryption and decryption) RSA Calculators (How the mathematics behind key creation and encryption works in practice) * https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html * https://www.cs.drexel.edu/~introcs/Fa12/notes/10.1_Cryptography/RSA_Express_EncryptDecrypt.html * http://extranet.cryptomathic.com/rsacalc/index * http://rsatools.wforums.net/#intro Simple Mathematics Example of RSA: p=7 q=11 for e1 public key=13 e2 private key=37 n=p*q=77 totient(n)= (7-1)*(11-1) =60 this must be 1: 13 mod 60 x 37 mod 60 = 481 mod 60 = 1 example: clear text message = 2 encrypted message = 30 encryption: e1 2^13 = 8192 8192 mod 77 = 30 decryption: e2 30^37 = 4.5028391e+54 4.5028391e+54 mod 77 = 2 Some links pointing out possible vulnerabilities and inconveniences: * https://gist.github.com/grugq/03167bed45e774551155 * http://arstechnica.com/security/2016/12/op-ed-im-giving-up-on-pgp/ * http://world.std.com/~dtd/sign_encrypt/sign_encrypt7.html * https://www.usenix.org/system/files/1401_08-12_mickens.pdf * https://thehackernews.com/2014/08/cryptography-expert-pgp-encryption-is_19.html You can’t trust the key based on metadata, or even short and long key fingerprints, they can also be faked: * https://evil32.com/ * https://twitter.com/bcrypt/status/765615853488316416 * https://twitter.com/isislovecruft/status/765660802120638464 * https://lists.gt.net/gnupg/devel/68250 * https://lkml.org/lkml/2016/8/15/445 * https://github.com/lachesis/scallion So always check full length fingerprint (160 bit or 40 hex characters) which you need to get from owner himself! Efforts on breaking the keys: * http://www.theregister.co.uk/2010/01/07/rsa_768_broken/ * https://eprint.iacr.org/2010/006.pdf * https://www.keylength.com/en/4/ * https://phys.org/news/2014-11-largest-factored-quantum-device.html * http://securityaffairs.co/wordpress/20637/hacking/acoustic-cryptanalysis-attack.html More links about PGP, GPG, and RSA Cicada 3301's Public Key * http://pastebin.com/sJiGQEPM * https://pgp.mit.edu/pks/lookup?op=vindex&search=0x181F01E57A35090F Script showing math behind public and personal keys are generated * https://www.cs.drexel.edu/~jpopyack/IntroCS/HW/RSAWorksheet.html Java online script to encode and decode RSA * http://merganser.math.gvsu.edu/m310.f99/encryption/encrypt.html Not terrible online java factorization (Factorization using the Elliptic Curve Method) * http://www.alpertron.com.ar/ECM.HTM * http://gilchrist.ca/jeff/factoring/nfs_beginners_guide.html * http://www.di-mgt.com.au/rsa_alg.html 2012 3301 final RSA puzzle: * http://pastebin.com/4nrDxVXk Perl script that solves 2012 RSA puzzle: * http://pastebin.com/NrDwJait (p and q values in it are factors from Triangle puzzle.) Manual key generation: * Create: 'https://www.igolder.com/pgp/generate-key/ * '''Upload: 'http://pgp.mit.edu/ Make sure you save your private key and remember (write down) the passphrase, if you lose that there is no recovery, and you won’t be able to decrypt messages you get from Cicada. '''How is RSA is a part of PGP: * http://openpgp.vie-privee.org/pgpfaq.html#HDPK * http://openpgp.vie-privee.org/pgpfaq.html#Note2 PGP servers: * http://www.rossde.com/PGP/pgp_keyserv.html ' MIT keyserver:' * http://pgp.mit.edu/ One of many backup servers you can use: * http://www.rediris.es/keyserver/ : Base 64 Base64 is a group of similar binary-to-text encoding schemes that represent binary data in an ASCII string format by translating it into a radix-64 representation. The term Base64 originates from a specific MIME content transfer encoding. Each base64 digit represents exactly 6 bits of data. Three 8-bit bytes (i.e., a total of 24 bits) can therefore be represented by four 6-bit base64 encodings. Base 64 Table The Base64 index table: When the number of bytes to encode is not divisible by three (that is, if there are only one or two bytes of input for the last 24-bit block), add extra bytes with value zero so there are three bytes, and perform the conversion to base64. If there is only one significant input byte (e.g., 'M'), all 8 bits will be captured in the first two base64 digits (12 bits).